1. Field of the Invention
This invention relates to the field of simulation, and in particular to the simulation of computer networks or other networks having bandwidth limitations that shape the traffic flow within the network.
2. Description of Related Art
As the demand for information flow continues to increase, establishing and maintaining an efficient network configuration to handle the increased flow typically requires complex analysis and planning. Generally, the analysis includes the identification of ‘bottlenecks’ where information flow is substantially impeded, or is expected to be impeded with future increases in traffic flow, and the planning includes the replacement or upgrading of equipment, or a reconfiguration of the network topology, to remove such bottlenecks, based on ‘what-if’ analyses of the benefits provided if such equipment or topology changes are made.
A common task for a network simulation system is “flow propagation analysis”, wherein the flow throughput is determined under a variety of traffic-flow scenarios. For example, a nominal data flow of 10 Mbps bandwidth may exist between a source device and a destination device, but if some of the 10 Mbps bandwidth elements between the source and destination device are also providing communication paths between other sources and destinations, the effective throughput between the original source and destination device will be dependent upon the amount of bandwidth consumed by the traffic-flow among the other communication paths. If a particular router, for example, is common to multiple high-traffic communication paths, and does not have sufficient bandwidth to support these multiple traffic flows, it will force the high-traffic flows to be ‘throttled’ to a lower-than-maximum throughput. Flow-propagation-analysis provides an assessment of the effective bandwidth available to each traffic flow, assuming a given traffic profile.
Computer-based analysis is commonly used to evaluate the performance of existing or proposed networks. Most analysis systems fall into one of two categories: analytical modeling systems and discrete-event simulation systems. In an analytical modeling system, mathematical equations, such as the equations that define the steady-state behavior of stochastic queues, are used to represent the performance of the network, and the analysis of the performance of the network involves determining a solution to the equations, given a set of input parameters. Analytic modeling, however, is generally infeasible for modeling the transient and/or adaptive behavior that is typical of a dynamic network.
In a discrete-event simulation system, a user describes the network as a collection of interconnected network elements. Each network element has an associated functional model that is configured to propagate the effects of an event at the element's input, to produce subsequent events at its output. The user also describes the activities that are to be simulated, and the simulation system generates discrete-events from these described activities at the appropriate elements, then propagates the effects of these events, and subsequently generated events at the outputs of each of the elements, from one element to the next, thereby simulating the behavior of each of the elements in response to the activities that are being simulated.
Discrete-event simulation systems are effective for modeling transient and/or adaptive behavior, because the model of each element can be configured to effect the desired behavior in response to incoming events, and the interconnection of elements can provide a model of the feedback among elements that often causes transients and/or adaptation. However, discrete-event simulations may exhibit poor performance, in terms of time taken to perform the simulation, because of the large number of events that can be triggered by each generated activity event, particularly in large networks with heavy traffic that include feedback paths, and when simulating concurrently generated activity events, such as generated traffic from multiple sources.
Of particular note, multiple-input limited-bandwidth network elements, such as a router or switch element, consume substantial simulation time to arrive at a steady-state assessment of the effective throughput of each traffic flow, because the propagation of an input event on one input channel of each multiple-input element is dependent upon the prior and concurrent arrival of events on other input channels, and, in the case of a prioritization scheme being applied among channels, may be dependent upon future arrivals of events on higher-priority channels.